//要求：滚筒洗衣机最少移动步数
//策略：不考虑具体移动过程，从每个洗衣机参与移动次数考虑，最少移动步数即最小移动过程中单个洗衣机最大移动次数
public class WaterMachinesMove {
}
class WaterMachinesMoveSolution {
    public int findMinMoves(int[] machines) {
        int n = machines.length;
        int[] nums = new int[n];
        nums[0] = machines[0];
        for(int i=1;i<n;i++){
            nums[i] = machines[i]+nums[i-1];
        }
        if(nums[n-1]%n!=0)return -1;
        int avr = nums[n-1]/n;
        int count = 0;
        for(int i=0;i<n;i++){
            int leftneed = avr*i;
            int rightneed = avr*(n-i-1);
            int left = i==0?0:nums[i-1];
            int right = nums[n-1]-nums[i];
            //当前洗衣机左右所有洗衣机所需要的衣服数量
            leftneed-=left;
            rightneed-=right;
            //所有移动都需要经过当前洗衣机，最大需求也是直接或间接由当前i洗衣机提供
            count = Math.max(count,Math.max(0,leftneed)+Math.max(0,rightneed));
        }
        return count;
    }
}